package com.itheima.leetcode.od.b.dynamicprogramming.kmp;

import com.itheima.leetcode.StrStrLeetcode28KMP;

import java.util.Arrays;
import java.util.stream.Collectors;

/**
 * (B卷,200分)- 最小循环子数组（Java & JS & Python & C）
 * <p>
 * 题目描述
 * <p>
 * 给定一个由若干整数组成的数组nums，请检查数组是否是由某个子数组重复循环拼接而成，请输出这个最小的子数组。
 * <p>
 * 输入描述
 * <p>
 * 第一行输入数组中元素个数n，1 ≤ n ≤ 100000
 * <p>
 * 第二行输入数组的数字序列nums，以空格分割，0 ≤ nums[i] < 10
 * <p>
 * 输出描述
 * <p>
 * 输出最小的子数组的数字序列，以空格分割；
 * <p>
 * 备注
 * 数组本身是其最大的子数组，循环1次可生成的自身；
 * <p>
 * 用例
 * <p>
 * 输入	9
 * 1 2 1 1 2 1 1 2 1
 * 输出	1 2 1
 * 说明	数组[1,2,1,1,2,1,1,2,1] 可由子数组[1,2,1]重复循环3次拼接而成
 */
public class MinimumCyclicSubarray {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        int[] nums = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();*/

        int[] nums = Arrays.stream("1 2 1 1 2 1 1 2 1".split(" ")).mapToInt(Integer::parseInt).toArray();
        System.out.println(getResult(nums));
        System.out.println(getResult2(nums));
    }

    /**
     * 方法一：kmp
     *
     * @param nums
     * @return
     */
    public static String getResult(int[] nums) {
        int n = nums.length;
        // KMP算法 前缀表求解
        char[] charArray = Arrays.stream(nums).
                boxed()
                .map(String::valueOf)
                .collect(Collectors.joining(""))
                .toCharArray();
        int[] next = StrStrLeetcode28KMP.lps(charArray);

        // 最长相同前后缀长度
        int m = next[n - 1];

        // 最小重复子串的长度
        int len = n % (n - m) == 0 ? n - m : n;

        return Arrays.stream(nums)
                .boxed()
                .limit(len)
                .map(String::valueOf)
                .collect(Collectors.joining(" "));
    }

    /**
     * 方法二：字符串replace暴力枚举
     *
     * @param nums
     * @return
     */
    public static String getResult2(int[] nums) {
        String input_str = Arrays.stream(nums)
                .boxed()
                .map(String::valueOf)
                .collect(Collectors.joining(""));
        for (int i = 1; i < input_str.length(); i++) {
            if (input_str.length() % i == 0) {
                String tmp = input_str;
                tmp = tmp.replace(input_str.substring(0, i), "");
                if (tmp.equals("")) {
                    return Arrays.stream(input_str.substring(0, i).split(""))
                            .collect(Collectors.joining(" "));
                }
            }
        }
        return null;
    }
}
